package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode842 
* @author      : ganwei 
* @date        : 2020年5月12日 
* @Description : Leetcode842 将数组拆分成斐波那契序列 
*/
public class Leetcode0842 {
	List<Integer> result = new ArrayList<Integer>();
	/**
	 * -解题思路，解法同累加数
	 */
    public List<Integer> splitIntoFibonacci(String s) {
    	backtrack(s, 0, 0, 0, new ArrayList<Integer>());
    	return result;
    }
    
    /**
     * -回溯主体
     */
    public boolean backtrack(String s, int start, int sum, int pre, List<Integer> il) {
    	if(start == s.length()) {
    		
    		if(il.size() > 2) {
    			result = new ArrayList<Integer>(il);
    			return true;
    		}
    		
    	}
    	for(int i = start; i < s.length(); i++) {
    		Integer cur = fetchCurValue(s, start, i);
    		if(cur < 0) {
    			continue;
    		}
    		if(il.size() >= 2 && sum != cur) {
    			continue;
    		}
    		
    		il.add(cur);
    		if(backtrack(s, i+1, cur+pre, cur, il)) {
    			return true;
    		}
    		il.remove(il.size()-1);
    	}
    	
    	
    	return false;
    }
    
    /**
     * -判断有效数字
     */
    public int fetchCurValue(String num, int l, int r) {
        if (l < r && num.charAt(l) == '0') {
            return -1;
        }
        
        int res;
        try {
        	res = Integer.valueOf(num.substring(l, r+1));
        }catch(NumberFormatException e) {
        	return -1;
        }

        return res;	
    }
    
    /**
     * 
     * @Title       : main 
     * @param       : @param args
     * @return      : void
     * @Description : TODO
     */
    
    public static void main(String[] args) {
    	Leetcode0842 l842 = new Leetcode0842();
    	l842.splitIntoFibonacci("123456579");
    	for(Integer i : l842.result) {
    		System.out.print(i);
    		System.out.print(" ");
    	}
    }
}
